package _17_剑指Offer;

import java.util.*;

public class _31_剑指Offer栈的压入弹出序列 {

    public static void main(String[] args) {

        _31_剑指Offer栈的压入弹出序列 v = new _31_剑指Offer栈的压入弹出序列();

        int[] pushed = {1, 2, 3, 4, 5};
        int[] popped = {3, 5, 4, 2, 1};
        System.out.println(v.validateStackSequences(pushed, popped));

    }

    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        for (int k : pushed) {
            stack.push(k);
            while (!stack.isEmpty() && stack.peek() == popped[j]) {
                stack.pop();
                j++;
            }
        }
        return stack.isEmpty();
    }

    public boolean validateStackSequences2(int[] pushed, int[] popped) {
        if (pushed.length == 0 && popped.length == 0) return true;
        int[] map = new int[1000];
        // 使用栈和队列模拟
        Stack<Integer> stack = new Stack<>();
        Queue<Integer> queue = new LinkedList<>();
        // 存储元素对应的索引
        for (int i = 0; i < pushed.length; i++) {
            map[pushed[i]] = i;
        }
        int index = map[popped[0]];
        // 前半部分数据入栈
        for (int i = 0; i < index; i++) {
            stack.push(pushed[i]);
        }
        // 后半部分入队列
        for (int i = index + 1; i < pushed.length; i++) {
            queue.offer(pushed[i]);
        }
        // 验证入栈序列是否成功
        for (int i = 1; i < popped.length; i++) {
            int ids = map[popped[i]];
            if (ids > index) {
                // 在队列中。 中间元素全部入栈
                for (int j = index + 1; j < ids; j++) {
                    stack.push(queue.poll());
                }
                // 当前元素出队
                queue.poll();
                index = ids;
            } else {
                // 在栈中， 是否为栈顶元素
                if (stack.pop() != popped[i]) {
                    return false;
                }
            }
        }
        return true;
    }

    public boolean validateStackSequences1(int[] pushed, int[] popped) {
        if (pushed.length == 0 && popped.length == 0) return true;
        Map<Integer, Integer> map = new HashMap<>();
        // 使用栈和队列模拟
        Stack<Integer> stack = new Stack<>();
        Queue<Integer> queue = new LinkedList<>();
        // 存储元素对应的索引
        for (int i = 0; i < pushed.length; i++) {
            map.put(pushed[i], i);
        }
        int index = map.get(popped[0]);
        // 前半部分数据入栈
        for (int i = 0; i < index; i++) {
            stack.push(pushed[i]);
        }
        // 后半部分入队列
        for (int i = index + 1; i < pushed.length; i++) {
            queue.offer(pushed[i]);
        }
        // 验证入栈序列是否成功
        for (int i = 1; i < popped.length; i++) {
            int ids = map.get(popped[i]);
            if (ids > index) {
                // 在队列中。 中间元素全部入栈
                for (int j = index + 1; j < ids; j++) {
                    stack.push(queue.poll());
                }
                // 当前元素出队
                queue.poll();
                index = ids;
            } else {
                // 在栈中， 是否为栈顶元素
                if (stack.pop() != popped[i]) {
                    return false;
                }
            }
        }
        return true;
    }

}
